package com.practice.dp;

public class SubsetSum {
	
	/*
	 * http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
	 * https://codeaccepted.wordpress.com/2014/02/27/dynamic-programming-subset-sum-problem/
	 */
	
	static boolean isSubsetSum(int set[], int n, int sum)
	{
	    // The value of subset[i][j] will be true if there is a subset of set[0..j-1]
	    //  with sum equal to i
	    boolean [][]subset = new boolean[sum+1][n+1];
	 
	    // If sum is 0, then answer is true
	    for (int i = 0; i <= n; i++)
	      subset[0][i] = true;
	 
	    // If sum is not 0 and set is empty, then answer is false
	    for (int i = 1; i <= sum; i++)
	      subset[i][0] = false;
	 
	     // Fill the subset table in botton up manner
	     for (int i = 1; i <= sum; i++)
	     {
	       for (int j = 1; j <= n; j++)
	       {
	         subset[i][j] = subset[i][j-1]; // since if j-1 elements has subset sum then j elements will have too.
	         if (i >= set[j-1])
	           subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1]; // since if j-1 elements has (i - set[j-1]) as 
	         	// subset sum, then adding i will also have subset sum
	       }
	     }
	 
	    /* // uncomment this code to print table
	     for (int i = 0; i <= sum; i++)
	     {
	       for (int j = 0; j <= n; j++)
	          System.out.println ("%4d", subset[i][j]);
	       System.out.println("\n");
	     } */
	 
	     return subset[sum][n];
	}
	 
	// Driver program to test above function
	public static void main(String[] args) {
		
	  int set[] = {3, 34, 4, 12, 5, 2};
	  int sum = 1;
	  int n = set.length;
	  if (isSubsetSum(set, n, sum) == true)
	     System.out.println("Found a subset with given sum");
	  else
	     System.out.println("No subset with given sum");
	}
}
